\vspace{10pt}
\section{Cost-driven 3D Design Optimization Flow}\label{sec:mechanism}

Based on the interconnect model and 3D cost model, cost-driven design optimization flow is implemented in block granularity to reduce system cost. In this section, we introduce the proposed design flow with metal layer reduction in detail.

%introduce the whole flow, block level partitioning
 
The flow takes the gate counts from synthesized design as input and outputs the cost-efficient 2D designs, TSV-based, and interposer-based 3D designs. Figure~\ref{fig:flow} shows the proposed cost-driven design optimization flow.
In this work, the 3D partitioning is in block granularity and each block contains arbitrary number of gates according to the block functionality.
 
\begin{figure}[htbp]
\begin{center}
	\includegraphics[width=0.40\textwidth]{./figures/flow.pdf}
\caption{Cost-driven design optimizaiton flow in 2D designs, TSV-based and interposer-based 3D designs with metal layer reduction technique.}
\vspace{-15pt}
\label{fig:flow}
\end{center}
\end{figure}

The 2D designs, TSV-based and interposer-based 3D designs after partitioning are generated with default area utilization. The minimum required metal layers for feasible routing are calculated using the interconnect model introduced in Section~\ref{sec:model}. The design costs are calculated based on the estimated chip area and metal layers.

In this flow, the important steps are area utilization estimation and corresponding metal layers estimation. The interconnect model in Section~\ref{sec:model} is used for metal layers estimation. However, the $l_i$, which is the maximum interconnect segment length that can be routed on metal layer $i$, is constrained by the routing resource. The routing resource on the other hand is bounded by the via area, which depends on $l_i$. For example, on metal layer $1$, if the maximum wire length that can be routed is $l_1$, then the wires that are longer than $l_1$ need to be put on higher metal layers, resulting in $I_{max} - I_1$ number of vias. The bigger $l_1$ value is, the less area occupied by vias. But the bigger $l_1$ needs more routing resource determined by available chip area. Finding the balanced $l_i$ for each metal layer is the key step in metal layer estimation. Searching all the possible combinations in sequence is extremely time consuming. In this work, we are using binary search algorithm shown in Algorithm~\ref{alg:algorithm}. The algorithm takes the chip area and wire pitches as input and gives the metal layers as output.

%how to get binary search?
\begin{algorithm}\scriptsize
\caption{Outline of the binary search algorithm for the estimation of metal layer requirement}
\label{alg:algorithm}
\begin{algorithmic}
\STATE Metal Layer Estimation (chip area, wire pitch)

\COMMENT{initialize layer count, $l_{max}$, $L(l_{max})$ and $I(l_{max})$}
\STATE layer count = 0, i = 0;
\WHILE{$l_i \le l_{max}$}
\STATE $l_i$ = (upbound+lowbound)/2;
\REPEAT
\STATE Calculated $k_i$ from  $l_i$;
\STATE Calculate $L(l_i)$ from $l_i$;
\IF{$L(l_i) - L(l_{i-1}) < k_i$}
\STATE Update the lowbound;
\ELSE
\STATE Update the upbound;
\ENDIF
\UNTIL{lowbound $>$ upbound }
\STATE Finish searching on metal layer i; i++;
\STATE Record $L(l_i)$ and $l_i$;

\COMMENT{find the balanced $l_i$}
\ENDWHILE
\STATE layer count = i;
\RETURN Layer count;
\end{algorithmic}
\end{algorithm}

Area utilization is the major factor that influences the fabrication cost. First, die yield is exponentially proportional to the die area which is calculated from area utilization. It means larger chip area results in significant higher cost. Second, the required metal layers are determined by the area utilization which determines the routing resource. Increased area utilization results in denser placement and more metal layers, implying higher mask cost. In this work, we consider the maximum area utilization that one design can achieve without sacrificing routability. \emph{Optimal area utilization} denotes the maximum utilization with default metal layers and \emph{maximum area utilization} is the maximum area utilization after one metal layer reduction. The design exploration flow finds the cost-efficient design through calculating the optimal and maximum area utilization. At physical design stage, CAD tools usually require designers to input the area utilization and perform placement and routing accordingly. However, sometimes the utilization is pessimistically estimated resulting in large unused chip area. So finding the best area utilization can help reduce the die area and design cost with feasible routing.

The same binary search algorithm is used for exploring the area utilization. In order to keep the design practical and reduce computation complexity, we set two utilization thresholds: the maximum and minimum thresholds, to control the searching range. The optimal area utilization is searched between the default utilization rate and maximum threshold. The maximum utilization rate without causing additional metal layers is the output. The maximum utilization rate after metal layer reduction should be between the minimum threshold and default utilization.

%only compute logic circuits or also include the memory?
The metal layer and area utilization estimations are suitable for generic logic designs. However, the estimation is inaccurate for regular pattern designs, such as cache and memory. In these regular designs, the routing complexity is not related to the number of gates and the metal layers are fixed once design pattern is known.
